package leetcode.L1000;

import java.util.Comparator;
import java.util.PriorityQueue;

public class EX767 {
    static class Newchar{
        int count;
        char letter;

        Newchar(int count,char letter){
            this.count = count;
            this.letter = letter;
        }
    }

    public static void main(String[] args) {
        String S = "aab";

        int[] couts = new int[26];

        for (int i = 0; i <S.length() ; i++) {
            couts[S.charAt(i)-'a']++;
        }

        PriorityQueue<Newchar> pq = new PriorityQueue<Newchar>(26, new Comparator<Newchar>() {
            @Override
            public int compare(Newchar o1, Newchar o2) {
                return o2.count-o1.count;
            }
        }) ;

        for (int i = 0; i < 26 ; i++) {
            if(couts[i]>0&&couts[i]<=(S.length()+1)/2){
                pq.add(new Newchar(couts[i],(char)(i+'a')));
            }
            else if(couts[i]>(S.length()+1)/2){
                return;
            }
        }

        StringBuilder str = new StringBuilder();
        while (pq.size()>1){
            Newchar c1 = pq.poll();
            Newchar c2 = pq.poll();

            str.append(c1.letter);
            str.append(c2.letter);

            if(--c1.count > 0) {pq.add(c1);}
            if(--c2.count > 0) {pq.add(c2);}
        }
        if(pq.size()>0){
            str.append(pq.poll().letter);
        }
        System.out.println(str.toString());
    }
}
